#include "../tools.h"

// void show(const priority_queue<pair<int, int>>& q){
//     while(q)
// }

class Solution {
public:
    struct cmp{
        bool operator()(const pair<int, int>& a, const pair<int, int>& b){
            // first 索引 second 值
            return a.second != b.second ? a.second < b.second : a.first > b.first;
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> qMax;
        int size = nums.size();
        for(int i = 0; i < k; ++i)
            qMax.push({i, nums[i]});
        
        vector<int> res;
        res.push_back(qMax.top().second);
        for(int i = k; i < size; ++i){
            qMax.push({i, nums[i]});

            auto e = qMax.top();
            // cout << i << ": " << e.first << " " << e.second << endl;
            while(e.first <= i - k) {
                qMax.pop();
                e = qMax.top();
            }
            res.push_back(e.second);
        }

        return res;
    }
};

int main(int argc, char const *argv[])
{
    Solution sol;

    vector<int> nums = {1};
    int k = 1;

    auto res = sol.maxSlidingWindow(nums, k);

    show(res);

    return 0;
}
